"""
参考拉不拉东
定义单调队列数据结构
push(n) {
    要保证队列是单调递减的；
    如果进入队列的元素比队列尾部元素大，就弹出较小的元素，
    最后，填充当前元素
}

max() {
    由于单调队列单调递减，队列头部元素就是最大值
    返回队列头部元素
}

pop(n) {
    队列是单调递减，
    如果队列头部元素==n，则弹出，
    否则直接结束函数
}

maxSlindWindow(nums,k) {
    创建空的单调队列，由于单调队列长短在变化，所以不需要指定长度
    创建返回结果列表res=[]

    遍历数组nums
    如果当前i<k-1，表示窗口差一个元素填满
        此时单调栈push元素nums[i],注意push内部会进行保证单调操作
    否则，表示当前窗口已经差一个填满
        先执行push操作，进行单调操作\
            (之所以将第一次填满放在else下面，是因为填满时候就会产生res[i])，\
            填满窗口
        res中添加单调栈栈顶元素，调用max函数
        执行pop(nums[i-k+1])操作，此时先删除nums[i-k+1]，使得窗口还差一个元素

}
"""
import collections

class MonoQueue(object):
    
    def __init__(self):
        self.mono_queue = collections.deque()
    
    def push(self, n):
        # 将比n小的元素都弹出
        while self.mono_queue and self.mono_queue[-1] < n:
            self.mono_queue.pop()
        # 删除小元素后，添加n
        self.mono_queue.append(n)

    def max_n(self):
        return self.mono_queue[0]

    def pop_n(self, n):
        if self.mono_queue[0] == n:
            self.mono_queue.popleft()
             
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """ 
        mono_queue = MonoQueue()
        res = []

        for i in range(len(nums)):
            if i < k - 1:
                mono_queue.push(nums[i])
            else:
                mono_queue.push(nums[i])
                res.append(mono_queue.max_n())
                mono_queue.pop_n(nums[i - k + 1])
        return res